package com.zjsru.plan2025.oneday;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 3065. 超过阈值的最少操作数 I
 *
 * @Author: cookLee
 * @Date: 2025-01-14
 */
public class MinOperations {

    /**
     * 主
     * \
     * 输入：nums = [2,11,10,1,3], k = 10
     * 输出：3
     * 解释：第一次操作后，nums 变为 [2, 11, 10, 3] 。
     * 第二次操作后，nums 变为 [11, 10, 3] 。
     * 第三次操作后，nums 变为 [11, 10] 。
     * 此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
     * 使数组中所有元素都大于等于 10 需要的最少操作次数为 3
     * \
     * 输入：nums = [1,1,2,4,9], k = 1
     * 输出：0
     * 解释：数组中的所有元素都大于等于 1 ，所以不需要对 nums 做任何操作。
     * \
     * 输入：nums = [1,1,2,4,9], k = 9
     * 输出：4
     * 解释：nums 中只有一个元素大于等于 9 ，所以需要执行 4 次操作。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        MinOperations minOperations = new MinOperations();
        int[] nums = new int[]{2, 11, 10, 1, 3, 4};
        int k = 10;
        System.out.println(minOperations.minOperationsV2Second(nums, k));
    }

    public int minOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = 0;
        for (int num : nums) {
            if (num < k) {
                ans++;
            }
        }
        return ans;
    }

    /**
     * 最小操作v2
     * \
     * 选择 nums 中最小的两个整数 x 和 y 。
     * 将 x 和 y 从 nums 中删除。
     * 将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。
     * \
     *
     * @param nums nums
     * @param k    k
     * @return int
     */
    public int minOperationsV2(int[] nums, int k) {
        Queue<Long> queue = new PriorityQueue<>();
        for (int num : nums) {
            queue.add((long) num);
        }
        int ans = 0;
        //下一个弹出的元素比k小即满足要求
        while (!queue.isEmpty() && queue.peek() < k) {
            if (queue.size() < 2) {
                return -1;
            }
            Long x = queue.poll();
            Long y = queue.poll();
            queue.offer(Math.min(x, y) * 2 + Math.max(x, y));
            ans++;
        }
        return ans;
    }

    /**
     * 最小操作v22
     *
     * @param nums nums
     * @param k    k
     * @return int
     */
    public int minOperationsV2Second(int[] nums, int k) {
        PriorityQueue<Long> q = new PriorityQueue<Long>();
        int ans = 0;
        for (int num : nums) {
            if (num < k) {
                q.add((long) num);
            }
        }
        while (q.size() >= 2) {
            ans++;
            long newNum = q.poll() * 2 + q.poll();
            if (newNum >= k) {
                break;
            }
            q.add(newNum);
        }
        //向上取整
        ans += Math.ceil(q.size() / 2.0);
        return ans;
    }

}
